home *** CD-ROM | disk | FTP | other *** search
/ Tech Arsenal 1 / Tech Arsenal (Arsenal Computer).ISO / tek-02 / sortdemo.zip / SDSORT05.INC < prev    next >
Text File  |  1992-04-15  |  4KB  |  104 lines
  1. (*
  2. ╔═══════════════════════════════════════════════════════════════════════════╗
  3. ║ Turbo Pascal 6.0 Include File : SDSORT05.INC                              ║
  4. ╟───────────────────────────────────────────────────────────────────────────╢
  5. ║ Program : SORTDEMO.PAS                                                    ║
  6. ╟───────────────────────────────────────────────────────────────────────────╢
  7. ║ Version : 1.0                                                             ║
  8. ╟───────────────────────────────────────────────────────────────────────────╢
  9. ║ Copyright (c) 1992  by  Jon S. Russell                                    ║
  10. ╟───────────────────────────────────────────────────────────────────────────╢
  11. ║ Quick-Sort #1 routine for SORTDEMO.PAS                                    ║
  12. ╚═══════════════════════════════════════════════════════════════════════════╝
  13.                                                                            *)
  14. procedure QuickSort1 (var Info  : InfoType;
  15.                           First : IndexType;
  16.                           Last  : IndexType);
  17. var
  18.   SplitPoint : IndexType;
  19.  
  20.   (*───────────────────────────────────────────────────────────────────────*)
  21.  
  22.   procedure Split (var Info       : InfoType;
  23.                        First      : IndexType;
  24.                        Last       : IndexType;
  25.                    var SplitPoint : IndexType);
  26.  
  27.     (* Choose SplitVal and rearrange List so that:       *)
  28.     (* List[First] .. List[SplitPoint-1] <= SplitVal and *)
  29.     (* List[SplitPoint] = SplitVal and                   *)
  30.     (* List[SplitPoint+1] .. List[Last] > SplitVal.      *)
  31.  
  32.   var
  33.     SplitVal  : ListElemType;  (* value on which to split *)
  34.     SaveFirst : IndexType;     (* original value of First *)
  35.  
  36.   begin  (* Split *)
  37.     (* SplitVal is chosen from the First array slot. *)
  38.     SplitVal := Info.List[First];
  39.  
  40.     (* Set up for split loop. *)
  41.     SaveFirst := First;
  42.     Inc(First);
  43.  
  44.     (* Loop Invariant: elements to the left of First are *)
  45.     (* less than or equal to SplitVal'  elements to the  *)
  46.     (* right of Last are greater than SplitVal           *)
  47.     repeat
  48.       (* Increment First until element > SplitVal. *)
  49.       while (First < Last) and (Info.List[First].Key <= SplitVal.Key) do
  50.         inc(First);
  51.  
  52.       (* Check end condition. *)
  53.       if (First = Last) and (Info.List[First].Key <= SplitVal.Key) then
  54.         inc(First);
  55.  
  56.       (* decrement Last until element > SplitVal. *)
  57.       while (First <= Last) and (Info.List[Last].Key > SplitVal.Key) do
  58.         dec(Last);
  59.  
  60.       (* If First and Last are on the wrong side of the *)
  61.       (* split point, then swap them;  update First and *)
  62.       (* Last to set up to continue splitting.          *)
  63.       if (First < Last) then
  64.         begin
  65.           Swap(Info, First, Last);
  66.           inc(First);
  67.           dec(Last);
  68.         end;
  69.     until First > Last;
  70.  
  71.     (* Set SplitPoint to place where the halves meet. *)
  72.     SplitPoint := Last;
  73.  
  74.     (* Swap SplitVal with element at SplitPoint. *)
  75.     Swap(Info, SaveFirst, SplitPoint);
  76.   end;   (* Split *)
  77.  
  78.   (*───────────────────────────────────────────────────────────────────────*)
  79.  
  80. begin  (* QuickSort1 *)
  81.   Info.Sorted := false;  (* reset flag *)
  82.  
  83.   if First < Last then  (* General Case *)
  84.     begin
  85.  
  86.       (* Procedure Split chooses the splitting value and *)
  87.       (* rearranges the array so that:                   *)
  88.       (* List[First] .. List[SplitPoint-1] <= SplitVal   *)
  89.       (* List[SplitPoint] = SplitVal AND                 *)
  90.       (* List[SplitPoint+1] .. List[Last] > SplitVal.    *)
  91.       Split(Info, First, Last, SplitPoint);
  92.  
  93.       (* Sort the left "half." *)
  94.       QuickSort1(Info, First, SplitPoint-1);
  95.  
  96.       (* Sort the right "half." *)
  97.       QuickSort1(Info, SplitPoint+1, Last);
  98.     end;
  99.  
  100.   Info.Sorted := true;  (* set flag *)
  101. end;   (* QuickSort1 *)
  102.  
  103. (*─────────────────────────────────────────────────────────────────────────*)
  104.